"""
题目：给定一棵二叉搜索树（BST）和一个目标值val，找到树中值等于val的节点并返回，若不存在则返回None。
"""

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def search_bst(root, val):
    """二叉搜索树的搜索（递归实现，利用BST特性减少比较）"""
    # 空节点或找到目标节点，返回当前节点
    if not root or root.val == val:
        return root
    # 目标值小于当前节点值：搜索左子树
    if val < root.val:
        return search_bst(root.left, val)
    # 目标值大于当前节点值：搜索右子树
    else:
        return search_bst(root.right, val)

def create_binary_tree(arr):
    if not arr:
        return None
    root = TreeNode(arr[0])
    queue = [root]
    index = 1
    while queue and index < len(arr):
        current = queue.pop(0)
        if arr[index] is not None:
            current.left = TreeNode(arr[index])
            queue.append(current.left)
        index += 1
        if index < len(arr) and arr[index] is not None:
            current.right = TreeNode(arr[index])
            queue.append(current.right)
        index += 1
    return root

# 测试
# BST结构：
#       4
#      / \
#     2   7
#    / \
#   1   3
root1 = create_binary_tree([4, 2, 7, 1, 3])
target_node1 = search_bst(root1, 2)
print(target_node1.val if target_node1 else None)  # 输出: 2
target_node2 = search_bst(root1, 5)
print(target_node2.val if target_node2 else None)  # 输出: None